package com.problem.leetcode;

import com.google.common.base.Stopwatch;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
 * <p>
 * Note: The solution set must not contain duplicate triplets.
 * <p>
 * For example, given array S = [-1, 0, 1, 2, -1, -4],
 * [-4,-1,-1,2-1,2]
 * <p>
 * A solution set is:
 * [
 * [-1, 0, 1],
 * [-1, -1, 2]
 * ]
 *
 * @author yanzhuoleo
 * @version V1.0
 * @Description: problem15
 * @date 2018-01-03-下午2:27
 */

public class Problem15 {
    public static void main(String[] args) {
        Stopwatch stopwatch = Stopwatch.createStarted();

        System.out.println(Problem15.threeSum(
                new int[]{3,-2,1,0}));

        stopwatch.stop();
        System.out.println(stopwatch.toString());
    }

    /**
     * TODO:性能
     * @param nums
     * @return
     */
    public static List<List<Integer>> threeSum(int[] nums) {

        List<List<Integer>> result = new ArrayList<List<Integer>>(1000);

        Arrays.sort(nums);
        long element = Long.MIN_VALUE;

        for (int index = 0; index < nums.length; ++index) {

            if (element == nums[index]) {
                continue;
            }
            element = nums[index];
            List<List<Integer>> lists = findTarget(nums, index + 1, nums.length - 1, -nums[index]);

            for (List<Integer> ele : lists) {
                ele.add(nums[index]);
            }
            if (!lists.isEmpty()) {
                result.addAll(lists);
            }
        }
        return result;

    }


    public static List<List<Integer>> findTarget(int[] nums, int begin, int end, int target) {

        List<List<Integer>> lists   = new ArrayList<List<Integer>>();
        HashSet<String>     hashSet = new HashSet<String>();
        while (begin < end) {
            if (nums[end] + nums[begin] > target) {
                --end;
                continue;
            }

            if (nums[end] + nums[begin] < target) {
                ++begin;
                continue;
            }

            if (nums[end--] + nums[begin++] == target && !hashSet.contains(
                    String.format("%s_%s", nums[begin - 1], nums[end + 1]))) {
                hashSet.add(String.format("%s_%s", nums[begin - 1], nums[end + 1]));
                List<Integer> result = new ArrayList<Integer>();
                result.add(nums[begin - 1]);
                result.add(nums[end + 1]);
                lists.add(result);
            }
        }
        return lists;
    }

}
